package structure.myBinaryTree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class BTNode{
    public char val;
    public BTNode left;
    public BTNode right;
    public BTNode (char val){
        this.val = val;
    }
}
public class MyBinaryTree {
    public BTNode root;//为什么定义在这里,因为根节点是二叉树的根而不是节点的根

    public BTNode createTree(){
        BTNode A = new BTNode('A');
        BTNode B = new BTNode('B');
        BTNode C = new BTNode('C');
        BTNode D = new BTNode('D');
        BTNode E = new BTNode('E');
        BTNode F = new BTNode('F');
        BTNode G = new BTNode('G');
        BTNode H = new BTNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }

    // 前序遍历
    void preOrder(BTNode root){
        if (root == null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

    // 中序遍历
    void inOrder(BTNode root){
        if (root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

    // 后序遍历
    void postOrder(BTNode root){
        if (root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }




    /**
     * 遍历思路
     * 求节点个数
     * @param root
     * @return
     */
    int count = 0;
    int size(BTNode root){
        if (root == null){
            return 0;
        }
            count++;
            size(root.left);
            size(root.right);
       return count;
    }

    /**
     * 子问题思路
     * 求节点个数
     * @param root
     * @return
     */
    int size1(BTNode root){
        if (root == null){
            return 0;
        }
         return size1(root.left) + size1(root.right) + 1;
    }


    /**
     * 遍历思路
     * 获取叶子节点的个数
     * @param root
     * @return
     */
    int sum = 0;
    int getLeafNodeCount(BTNode root){
        if (root == null){
            return 0;
        }
        if (root.right == null && root.left == null){
            sum++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return sum;
    }

    /**
     * 子问题思路
     * 获取叶子节点的个数
     * @param root
     * @return
     */
    int getLeafNodeCount1(BTNode root){
        if (root == null){
            return 0;
        }
        if (root.right == null && root.left == null){
            return 1;
        }
        return getLeafNodeCount1(root.left)+getLeafNodeCount1(root.right);
    }

    /**
     * 遍历思路
     * 获取第K层节点的个数
     * @param root
     * @return
     */
    int count1 = 0;
    int getKLevelNodeCount(BTNode root,int k){
        if (root == null){
            return 0;
        }
        if (k == 1) {
            count1++;
            return 1;
        }
        getKLevelNodeCount(root.left,k-1);
        getKLevelNodeCount(root.right,k-1);
        return count1;
    }

    /**
     * 子问题思路
     * 获取第K层节点的个数
     * @param root
     * @return
     */
    int getKLevelNodeCount1(BTNode root,int k){
        if (root == null || k <= 0){
            return 0;
        }
        if (k == 1){
            return 1;
        }
        return getKLevelNodeCount1(root.left,k-1) + getKLevelNodeCount1(root.right,k-1);
    }

    /**
     * 获取二叉树的高度
     * @param root
     * @return
     */
    int getHeight(BTNode root){
        if (root == null){
            return 0;
        }
        return  Math.max(getHeight(root.left),getHeight(root.right)) + 1;
    }

    /**
     * 检测值为value的元素是否存在
     * @param root
     * @param val
     * @return
     */
    BTNode find(BTNode root, char val){
        if (root == null) return null;
        if (root.val == val) return root;

        BTNode ret = find(root.left,val);
        if (ret != null){
            return ret;
        }
        ret = find(root.right,val);
        if (ret != null){
            return ret;
        }
        return null;
    }

    /**
     * 判断一棵树是不是完全二叉树
     * @param root
     * @return
     */
    boolean isCompleteTree(BTNode root){
        if (root == null) return true;
        Queue<BTNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            BTNode cur = queue.poll();
            if (cur != null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        while (!queue.isEmpty()){
            BTNode top = queue.peek();
            if (top != null) return false;
            queue.poll();
        }
        return true;
    }


}
